﻿using System;
using System.Collections.Generic;

namespace SortOf
{
    public class Graph
    {
        private const int NUM_VERTICES = 20;
        private Vertex[] vertices;
        private int[,] adjMatrix;
        int numVerts;

        public Graph()
        {
            vertices = new Vertex[NUM_VERTICES];
            adjMatrix = new int[NUM_VERTICES, NUM_VERTICES];
            numVerts = 0;
            for (int j = 0; j < NUM_VERTICES; j++)
            {
                for (int k = 0; k < NUM_VERTICES; k++)
                {
                    adjMatrix[j, k] = 0;
                }
            }
        }

        public void AddVertex(IComparable label)
        {
            vertices[numVerts] = new Vertex(label);
            numVerts++;
        }

        public void AddEdge(int start, int end)
        {
            adjMatrix[start, end] = 1;
            //adjMatrix[end, start] = 1;
        }

        public void ShowVertex(int i)
        {
            Console.Write(vertices[i].label.ToString() + " ");
        }

        public int NoSuccessors()
        {
            bool isEdge;
            for (int row = 0; row < NUM_VERTICES; row++)
            {
                isEdge = false;
                for (int col = 0; col < numVerts; col++)
                {
                    if (adjMatrix[row, col] == 1)
                    {
                        //Console.WriteLine("Found on " + row + "," + col + " -- " + adjMatrix[row, col]);
                        isEdge = true;

                    }
                }

                if (!isEdge)
                {
                    return row;
                }
            }

            return -1;
        }

        public void ShiftRow(int row)
        {
            for (int col = 0; col < numVerts; col++)
            {
                adjMatrix[row, col] = adjMatrix[row + 1, col];
            }
        }

        public void ShiftCol(int col)
        {
            for (int row = 0; row < numVerts; row++)
            {
                adjMatrix[row, col] = adjMatrix[row, col + 1];
            }
        }

        public void DeleteVertex(int vertexPosition)
        {
            if (vertexPosition != (numVerts))
            {
                for (int j = vertexPosition; j < numVerts; j++)
                {
                    vertices[j] = vertices[j + 1];
                }

                //for (int row = vertexPosition; row < numVerts; row++)
                //{
                //    ShiftRow(row);
                //}
                for (int col = vertexPosition; col < numVerts; col++)
                {
                    ShiftCol(col);
                }
                numVerts--;
            }
        }

        public void ShowEdge()
        {
            for (int y = 0; y < numVerts; y++)
            {
                for (int x = 0; x < numVerts; x++)
                {
                    Console.Write(adjMatrix[y, x] + " ");
                }
                Console.WriteLine();
            }
        }


        public void TopSort()
        {
            System.Collections.Generic.Stack<Vertex> sortStack = new System.Collections.Generic.Stack<Vertex>();
            while (numVerts > 0)
            {
                //this.showEdge();
                int top = NoSuccessors();
                //Console.WriteLine(top);
                //Console.WriteLine(numVerts);
#if DEBUG
                Console.WriteLine("//----------[Verticles left: " + numVerts + "]----------//");
                this.ShowEdge();
                Console.WriteLine("//---------------------------------------//");
                Console.WriteLine();
#endif
                if (top == -1)
                {
#if DEBUG
                    Console.WriteLine("Error: geen top gevonden ");
#endif

                    return;
                }

                for (int i = NUM_VERTICES - 1; i >= 0; i--)
                {

                    if (adjMatrix[top - 1, i] == 1)
                    {

                        sortStack.Push(vertices[i]);
                        //Console.WriteLine(vertices[i].label.ToString());
                        DeleteVertex(i);
                        //Console.WriteLine("Deleted line " + i);
                    }
                }
                //this.showEdge();
            }

            Console.WriteLine("Topologocal sorting order:");
            while (sortStack.Count > 0)
            {
                Console.Write(sortStack.Pop().label.ToString() + " ");
            }
        }


        #region Search
        /// <summary>
        /// Get the index of an adjecent vertex that has not been visited yet.
        /// </summary>
        /// <param name="v">The index of the vertex from which we want to check the neighbouring vertices.</param>
        /// <returns>The index of the adjacent vertex that is unvisited.</returns>
        private int GetAdjacentUnvisitedVertex(int v)
        {
            for (int i = 0; i < numVerts; i++)
            {
                if (adjMatrix[v, i] == 1 && !vertices[i].wasVisited)
                {
                    return i;
                }
            }

            return -1;
        }

        /// <summary>
        /// Depth-first search involves following a path from the beginning vertex until it reaches
        /// the last vertex, then backtracking and following the next path until it reaches the
        /// last vertex, and so on until there are no more paths left.
        /// </summary>
        public void DepthFirstSearch()
        {
            System.Collections.Generic.Stack<int> gStack = new System.Collections.Generic.Stack<int>();

            // Vertex with an id of zero.
            vertices[0].wasVisited = true;
            ShowVertex(0);
            gStack.Push(0);

            while (gStack.Count > 0)
            {
                int v = GetAdjacentUnvisitedVertex(gStack.Peek());

                if (v == -1)
                {
                    gStack.Pop();
                }
                else
                {
                    vertices[v].wasVisited = true;
                    ShowVertex(v);
                    gStack.Push(v);
                }
            }

            for (int i = 0; i < numVerts; i++)
            {
                vertices[i].wasVisited = false;
            }
        }

        /// <summary>
        /// A breadth-first search starts at a first vertex and tries to
        /// visit vertices as close to the first vertex as possible.
        /// </summary>
        public void BreadthFirstSearch()
        {
            BreadthFirstSearch(0);
        }

        /// <summary>
        /// A breadth-first search starts at a first vertex and tries to
        /// visit vertices as close to the first vertex as possible.
        /// </summary>
        /// <param name="index">The index of the vertex at which to start the search.</param>
        public void BreadthFirstSearch(int index)
        {
            // Apparently there is one within the Generic namespace too!
            System.Collections.Queue gQueue = new System.Collections.Queue();

            vertices[index].wasVisited = true;
            ShowVertex(index);
            gQueue.Enqueue(index);

            int vert1, vert2;
            while (gQueue.Count > 0)
            {
                vert1 = (int)gQueue.Dequeue();
                vert2 = GetAdjacentUnvisitedVertex(vert1);

                while (vert2 != -1)
                {
                    vertices[vert2].wasVisited = true;
                    ShowVertex(vert2);
                    gQueue.Enqueue(vert2);
                    vert2 = GetAdjacentUnvisitedVertex(vert1);
                }
            }

            for (int i = 0; i < numVerts; i++)
            {
                vertices[i].wasVisited = false;
            }
        }
        #endregion
    }
}
